package interview.Algorithms;


public class MinPriorityQueue<key extends Comparable <key> > {
	private key[] pq;
	private int item;
	@SuppressWarnings("unchecked")
	public MinPriorityQueue(int size){
		pq = (key[])new Comparable[size];
		item = 0;
	}
	public Boolean isFull(){
		return (item==pq.length);
	}
	
	public Boolean isEmpty(){
		return (item == 0);
	}
	
	public void insert (key data){
		if (isFull()) return; 
		pq[item++]=data;
		buildHeap();
	}
	
	private boolean less(int i , int j){
		if((pq[i]==null) || (pq[j] == null)) return true;
		return (pq[i].compareTo(pq[j]) < 0);
	}
	
	private void swap(int i , int j){
		key temp = pq[i];
		pq[i] = pq[j];
		pq[j] = temp;
	}
	
	private void buildHeap(){
		int cindex = item-1;
		int pindex ;
		if(cindex%2==0) pindex = (cindex - 2)/2;
		else pindex = (cindex - 1)/2;
		if((cindex<0)||(pindex<0))return;
		while(less(cindex,pindex)){
			swap(pindex, cindex);
			cindex = pindex;
			if(pindex%2==0) pindex = (pindex-2)/2;
			else pindex = (pindex-1)/2;
			if((cindex<0)||(pindex<0))break;
		}				
	}
	public key deleteMin(){
		int lindex, rindex,index=0;
		key minKey = pq[0];
		
		if((item==0) ||(item==1)){
			if(item==1)
				pq[0]=pq[1];
			
			pq[item]=null;
			item--;
			return minKey;	
		}
		swap(0, (--item));		
		
		lindex = index+1;
		rindex = index+2;
		
		if(item==2){
			if(!less(index,lindex))
				swap(lindex, index);
			pq[item]=null;
			return minKey;	
		}
		
		while( !less(index,rindex) || !less(index ,lindex)){				
			if(less(lindex,rindex)){ 
				swap(index, lindex)	;
				index = lindex;
			}
			else {
				swap(index, rindex); 
				index = rindex;
			}
			lindex = (2 * index) +1;
			rindex = (2 * index) + 2;
			if ((lindex>item-1) || (rindex>item-1)){
				if ((lindex>item-1) && (rindex>item-1)){
					break;
				}
				else if(rindex>item-1){
					if(!less(index,lindex))
						swap(lindex, index);
					break;
				}
				else{
					if(!less(index,rindex))
						swap(rindex, index);
					break;						
				}
			}				
		}
	//System.out.println("Item count :" + item);
	pq[item]=null;
	return minKey;	
	} 
}
